#pragma once
#include "macro.h"
#include "memory"
#include "stack.h"

namespace galois::data {
template <class T, int N, int BLOCK = 1>
class RingPtr1W1R {
public:
  RingPtr1W1R() : r_(0), w_(0) {
  }
  T *Get() {
    uint64_t addr = w_.load(std::memory_order_relaxed);
    uint64_t raddr = r_.load(std::memory_order_relaxed);
    uint64_t use_addr = use_.load(std::memory_order_relaxed);
    if constexpr (BLOCK == 1) {
      if (unlikely(addr - raddr >= N)) { return nullptr; }
    }
    if (use_addr < raddr || addr - raddr >= N) { return data[use_addr % N]; }
    return new T();
  }
  void revert(T *val) {
    uint64_t use_addr = use_.load(std::memory_order_relaxed);
    if (val != data[use_addr % N]) delete val;
  }
  bool push(T *val) {
    uint64_t addr = w_.load(std::memory_order_relaxed);
    uint64_t use_addr = use_.load(std::memory_order_relaxed);
    data[addr % N] = val;
    w_.fetch_add(1, std::memory_order_release);
    if (val == data[use_addr % N]) use_.fetch_add(1, std::memory_order_release);
    return true;
  }
  bool pop(const std::function<void(T *)> &f) {
    uint64_t r = r_.load(std::memory_order_relaxed);
    uint64_t w = w_.load(std::memory_order_acquire);
    if (r >= w) return false;
    T *ret = data[r % N];
    if constexpr (BLOCK == 0) {
      do {
        if (unlikely(w - r >= N)) {
          r = w - N + 1;
          ret = data[r % N];
        }
        w = w_.load(std::memory_order_acquire);
      } while (w - r >= N);
    }
    f(ret);
    r_.store(r + 1, std::memory_order_release);
    return true;
  }
  void move(int n) {
    r_.fetch_add(n, std::memory_order_release);
  }
  uint64_t size() {
    return w_.load(std::memory_order_acquire) - r_.load(std::memory_order_relaxed);
  }

private:
  T *data[N];
  std::atomic<uint64_t> r_;
  std::atomic<uint64_t> use_;
  std::atomic<uint64_t> w_;
};

template <class T, int N>
class RingPtrNWNR {
public:
  RingPtrNWNR() : r_(0), w_(0) {
  }
  bool push(T *val) {
    uint64_t addr = w_.load(std::memory_order_relaxed);
    auto raddr = r_.load(std::memory_order_relaxed);
    do {
      if (unlikely(addr - raddr >= N)) return false;
    } while (!w_.compare_exchange_weak(addr, addr + 1, std::memory_order_release, std::memory_order_relaxed));
    data[addr % N] = val; //  addr add but val is old. repair in pop
    return true;
  }
  T *pop() {
    uint64_t r = r_.load(std::memory_order_acquire);
    uint64_t w = w_.load(std::memory_order_acquire);
    int addr = 0;
    T *ret = nullptr;
    do {
      if (r >= w) return nullptr;
      addr = r % N;
      while (unlikely(data[addr] == nullptr)) {
        uint64_t r1 = r_.load(std::memory_order_acquire);
        if (r == r1) return nullptr;
        r = r1;
        addr = r % N;
      }
      ret = data[addr];
    } while (!r_.compare_exchange_weak(r, r + 1, std::memory_order_release, std::memory_order_relaxed));
    data[addr] = nullptr;
    return ret;
  }
  uint64_t size() {
    return w_ - r_;
  }

private:
  T *data[N];
  std::atomic<uint64_t> r_;
  std::atomic<uint64_t> w_;
};

#pragma once
#include <memory>
#include <vector>

namespace galois::base
{
    template <class T>
    class DataSpan
    {
    private:
        const T **data;
        uint64_t mono_start_addr;
        const uint64_t* mono_end_addr;
        const uint32_t capacity;

    public:
        span(T **d, uint64_t start, uint64_t* end, uint32_t s) : data(d), mono_start_addr(start), mono_end_addr(end), capacity(s) {}
        /**
         * 数据计算了多少次
         */
        const uint64_t end() const
        {
            return *mono_end_addr;
        }
        const uint64_t start() const
        {
            return mono_start_addr;
        }
        /**
         * 当前span的数据大小
         */
        const int size() const
        {
            return *mono_end_addr - mono_start_addr;
        }
        /**
         * before [], you should check if the index is valid
         */
        const T *operator[](int index) const
        {
            return data[index];
        }
        const T* GetLastAndClearOthers()
        {
            int len = size();
            if(len == 0){
                return nullptr;
            }
            if(len > 1){
                remove(len - 1);
            }
            return data[len - 1];
        }
        const T* GetLast() const
        {
            int len = size();
            if(len == 0){
                return nullptr;
            }
            return data[len - 1];
        }
        void remove(int num)
        {
            auto s0 = mono_start_addr%capacity;
            mono_start_addr += num;
            auto s1 = mono_start_addr%capacity;
            data += s1 - s0;
        }
    };

    template <class T, int N>
    class DataElement
    {
    public:
        bool push(std::function<void(T *val)> &fill)
        {
            if(get()){
                auto addr = mono_addr_ % N;
                fill(data_[addr]);
                data_[addr + N] = data_[addr];
                ++mono_addr_;
                return true;
            }
            return false;
        }

    private:
        std::vector<DataSpan<T>> spans_;
        T *data_[2*N];
        uint64_t mono_addr_ = 0;
        uint64_t start_ = 0;
        T* Get()
        {
            auto addr = mono_addr_ % N;
            uint64_t n = start_ + N;
            for(auto &span : spans_){
                if(span.start() < n){
                    n = span.start();
                }
            }
            if(mono_addr_ - n >= N){
                return nullptr;
            }
            if constexpr (has_clear_v<T>){
                if(start_ < n){
                    data_[addr] = data_[start_ % N];
                    start_++;
                    data_[addr]->Clear();
                }
            }else{
                while(start_ < n){
                    delete data_[start_ % N];
                    ++start_;
                }
            }
            if(!data_[addr]){
                    data_[addr] = new T();
            }
            return data_[addr];
        }
    };
}

} // namespace galois::data
